public class SolutionOfferII29 {

    static class Node {
        public int val;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }

    public Node insert(Node head, int insertVal) {
        if (head==null){
            Node node=new Node(insertVal);
            node.next=node;
            return node;
        }
        Node t=head;
        if (insertVal>=head.val){
            while (t.next!=head && t.next.val<=insertVal && t.next.val>=head.val){
                t=t.next;
            }
        }else {
            while (t.next!=head && t.next.val>=t.val){
                t=t.next;
            }
            while (t.next!=head && t.next.val<=insertVal){
                t=t.next;
            }
        }
        t.next=new Node(insertVal,t.next);
        return head;
    }

    public static void main(String[] args) {
        Node head=new Node(3);
        Node t2=new Node(4);
        Node t3=new Node(1);
        head.next=t2;
        t2.next=t3;
        t3.next=head;
        System.out.println(new SolutionOfferII29().insert(head,2).next.next.next.val);
    }
}
